1. Field of the Invention
The invention relates generally to optical scanners having an improved linearized raster scanning pattern for two-dimensional imaging. It relates particularly, though not exclusively, to scanners for reading bar code symbols having vertically-modulated symbologies such as POSTNET or PostBar.
2. Description of Related Art
Conventional optical scanners such as bar code readers normally operate by scanning a laser beam across a bar code symbol or optical indicia to be read. Light reflected from the symbol or indicia is detected, digitized and decoded to extract the information represented by the symbol or indicia. Frequently, the symbol or indicia is one-dimensional and is scanned merely by oscillating a fixed laser beam back and forth to form a scan line. Recently, however, there has been increased interest in two-dimensional symbols or indicia, not least because of the greater information content that they can carry.
Imaging in two dimensions is somewhat more complex than imaging in one dimension. One possible approach for two-dimensional imaging is to make use of two-dimensional arrays of charge coupled devices (CCDs) or photodiode arrays, for example as is disclosed in U.S. Pat. No. 4,408,334. Neither has become particularly popular in practice, however, primarily because of the cost. Two-dimensional arrays are relatively difficult and expensive to manufacture, and, as in any semi-conductor technology, many dies are produced having defects which prevent them from imaging over their entire surface. Such defective arrays are frequently not usable in high resolution imaging applications.
An alternative approach to two-dimensional imaging is to use a scanner, for example a laser scanner, which scans the beam in a two-dimensional raster pattern across the symbol or indicia to be read. Problems have been encountered in practice, however, in that it is difficult to capture a two-dimensional image using this particular technology without substantial distortions. Distortions tend to be particularly severe in the vertical or y direction, that is in the direction which is perpendicular to the individual scan lines. The distortions are due to the nonlinear response of the scanning element. These have proved in practice difficult to eliminate.
A standard raster pattern is normally generated using sinusoidal signals both on the horizontal (x) and vertical (y) axes. However, the image captured with such a pattern will not have a uniform resolution along the y-axis. The scan lines tend to bunch together at the top and bottom of each frame, thereby wasting scan lines at the edges and producing rather sparse coverage in the center of the frame. It might be thought that the obvious solution to linearizing the y axis would be to replace the sinusoidal with a linear (triangular) y-axis drive signal. However, the applicants have found that when the scan element is driven with such a triangular waveform the distortions tend to become even worse. The reason is that a triangular waveform has many harmonics that interact with the many resonant modes of the scan element (oscillating mirror) thereby producing unpredictable and somewhat erratic behavior.
As the image becomes distorted, the following problems arise:
1. Decreased working range. This arises because as the required working distance increases, the diverging y-axis scan amplitude further separates the already sparse areas of scan line distribution in the center of the frame. If the working distance is too high, the scan lines in the center of the frame may be too widely spaced to allow effective image capture. PA0 2. Difficulty in aiming the scanning pattern at the indicia to be decoded. If the scanning pattern is not uniform across the frame, the user tends to find in practice that the indicia has to be located at the densest part of the scan pattern in order to ensure an easy decode. If the scan line distribution were to be uniform within the scanning frame, this problem would not arise as the indicia could be decoded with the same ease anywhere within that frame. PA0 3. There is less tolerance to tilting the indicia, since the uneven y-axis resolution tends to warp the image. PA0 4. There is less reading robustness since geometric shapes become severely distorted. PA0 1. Usually image processing software requires a lot of memory. We achieve our goal without increasing the RAM hardware requirement. This is achieved by processing the DBP data as they come in and constructing an image-understanding model based on our expected target. The expected target is a series of vertical bars with different heights but the same width. The image understanding model is the Line Adjacency Graph (LAG). We use a simplified LAG structure which uses very limited RAM. No image needs to be created in memory. (This feature is suitable also for scanners with a linear CCE as input device). PA0 2. Usually image processing software requires a lot of processing time or CPU power. The LAG structure we use is easy to compute, thus can be calculated as data comes in. In addition, we split the image processing into two parts: per-line processing and per-frame processing. Per-line processing builds the image understanding model, which mainly consists of x-synchronization, noise removal and LAG construction. Per-frame processing attempts to decode the result from the LAG structure. PA0 3. In our approach, we provide an x-synchronization through the use of a hardware "guard-bar", and a y-synchronization through the use of a pair of clocks: the master clock and slave clock. The use of two clocks ensures that when we lose count because of processing falling behind the data gathering, we can re-synchronize at the start of the next frame. PA0 4. We achieve auto-discrimination between postal codes, PDF and linear codes by separating data frames into PostBar-frames and non-PostBar-frames. During a PostBar-frame, the Postbar per-line processing is invoked. During a non-PostBar-frame, the PostBar per-frame processing is done first on the LAG built during the previous PostBar-frame, and then the decoder time is given back to the regular linear and PDF decoders. Whichever code decoded first ends the decode session. PA0 5. A PostBar symbol requires relatively dense scan line y-coverage, while a PDF symbol requires a sufficient height in y-coverage. To allow both to be decoded by the same scanner, we use a mode-switching mechanism. The scanner starts off in a "PostBar" mode, in which a "slab scan pattern" with dense y-pattern is created. In this mode, both PostBar symbols and linear symbols can be decoded with ease. Although during this time a PDF code could be found, it may not be decoded if it has a height larger than that of the slab. Once the PDF label is found, the scanner brakes the y-scan first (allowing further gathering of data in this mode), then switches to a large y-raster. This allows a PDF label with large y-size to be covered by the scan pattern. PA0 6. The scanner may, in practice, have a different x-speed profile for the forward and for the reverse scans. To make use of both of these, we create separate data structures for them and process them separately until the LAGs are completed. If neither one can be decoded alone, we attempt to merge the LAGs from forward and reverse scan lines. This merged LAG has a higher y-resolution than the resolution of either forward or reverse scans alone. PA0 7. Once the trigger is pulled, the scanner tries to decode the PostBar pattern up to 18 times per second. This feature greatly increases the chance of decode. (This logic can also be used with scanners using a 2-D CCD as input device). PA0 8. Some data in the PostBar symbology are not protected by any means. To reduce the error rate, we compare two subsequent decoding results of the unprotected data and only report a successful decode when the two are identical. PA0 9. Many parameters are used to define the PostBar's size and features. These parameters are adapted when data are being processed and features found. We use a class of digital adaptive filters with the general formula y+(x-y)/m, where x is the input value, y is the parameter which is to be adapted towards x, and m is the "length" of the filter. Usually, m=2.sup.n, where n is an integer, so the division can be done in an efficient right shift operation. This type of filters are similar to the average filter over the last m input values, but is much easier to compute and costs less memory space.
Certain bar code symbologies encode data by means of the relative heights of bars on an essentially one-dimensional pattern. An example of such a symbology is the Postal Numeric Encoding Technique (POSTNET) developed by the US postal service to provide an optimized bar code system for encoding address information on letter mail. The basic elements of a POSTNET code, shown in FIG. 3, are tall bars 110 and short bars 112, representing respectively binary ones and zeros. Both the tall bars and the short bars are horizontally aligned along the bottom edge of the symbol. Five bars of code represents one character. One method of decoding symbologies of this type is disclosed in U.S. Pat. No. 5,369,264 which uses a one-dimensional scanner having an elongate scanning area which extends in the direction parallel to the bars of the symbol.
It is an object of the invention to provide a two-dimensional optical scanner having improved linearity, particularly in the vertical or y direction.